1. Field of the Invention
The present invention relates to a digital communication system using error-correcting codes, and more particularly a method of transmitting and receiving data using quasi-cyclic low density parity check codes and an apparatus therefor.
2. Description of the Related Art
Generally speaking, a digital communication system provides effective and reliable transmission of data through a channel. The next generation multimedia mobile communication system being recently and vigorously developed demands the capabilities of treating and transmitting varieties of information such as video data and text data together with voice communication at high speeds. Accordingly, to meet such demand, it is essential to improve the efficiency of the system by applying a suitable channel coding technique thereto.
Meanwhile, the wireless channel environment for the digital communication system inherently causes multi-path interference, shadowing, wave damping, noises, fading, etc., which is different from the wireless environment, resulting in information loss that distorts the transmitted signals. In order to cope with such information loss various error-control techniques adapted for the channel characteristics in the communication system have been proposed. Among them one of the most basic techniques is to use the error-correcting code.
The next generation communication system has been developed to provide communication services for transmitting a large amount of data at high speed with various QoS (Quality of Service). Hence, the error-correcting capability of the error-correcting code critically determines the QoS of the entire data service to prevent information loss. Typical examples of an error-correcting code include turbo code, low density parity check (LDPC) code, etc.
The LDPC code has been known to have good performance gain in data transmission at high speed compared to the conventional convolution code which is chiefly used for correction of errors. It is advantageous in effectively correcting the errors caused by noises occurring in the wireless channel to enhance the reliability of data transmission. The LDPC code also has an advantage in that it may perform decoding by using an iterative decoding algorithm based on the sum-product algorithm using a factor graph. The decoder of the LDPC code has lower complexity than that of the turbo code, and better feasibility in designing a parallel processing decoder.
The turbo code has good performance approaching the channel capacity limit of Shannon's Channel Coding Theorem while the LDPC code shows performance with a deviation of about 0.04 dB from the channel capacity limit of Shannon's Channel Coding Theorem at a BER (Bit Error Rate) of 10−5 using a block size of 107. Shannon's Channel Coding Theorem represents the possibility of reliable communication with a data rate not exceeding the channel capacity. However, Shannon did not show how to perform coding and decoding practically in order to not exceed the channel capacity limit. Though a random code with a considerably large block size shows performance approximating the channel capacity limit of Shannon's Channel Coding Theorem, the MAP (Maximum A posteriori) or ML (Maximum Likelihood) decoding thereof is practically impossible due to the huge load resulting from the very large amount of required calculation.
Meanwhile, there exist cycles in the factor graph describing the LDPC code, where iterative decoding has been known to be suboptimal. Nevertheless, it has been experimentally discovered that the LDPC code shows good performance through iterative decoding. But if the number of the cycles having a shorter length is increased, degradation of performance may be expected, and a lot of effort has been made to design an LDPC code having no shorter cycle. For example, the LDPC code proposed by Gallagher is defined by a parity check matrix, of which a large number of elements have the value of 0 (null) and the remaining very small number the value of 1. Namely, the parity check matrix of the LDPC code has a very small weight, so that even a relatively long block code may be decoded through iterative decoding. Further, by continuously increasing the length of the block code, the LDPC code shows performance closely approaching the channel capacity limit of Shannon. Hence, the LDPC code tends to be positively used as the error-correction code in the next generation communication system.
Meanwhile, the LDPC code (N, j, k) is a linear block code with a block size N, having a parity check matrix of a sparse structure that consists of a number j of is per each column, a number k of is per each row, and the remaining elements of 0. Such a parity check matrix with a constant column weight j and a constant row weight k is called a regular LDPC code. On the contrary, the parity check matrix with non-constant column and row weights is called an irregular LDPC code. In this case, the term “weight” means the number of the elements with a non-zero value. Generally the irregular LDPC code has been known to have better performance as compared to the regular LDPC code. However, in order to obtain an irregular LDPC code with good performance, it should be suitably selected the number of 1s per row and per column.
Referring to FIGS. 1 and 2, a parity check matrix (N=8, j=2, k=4) of the LDPC code is described. FIG. 1 shows the parity check matrix H, and FIG. 2 shows the factor graph of the parity check matrix. The parity check matrix H (8, 2, 4) of the LDPC code consists of 8 columns respectively having the same weight of two is and 4 rows respectively having the same weight of four 1s, as shown in FIG. 1.
FIG. 2 shows the factor graph of the parity check matrix (8, 2, 4) of the LDPC code, consisting of eight variable nodes 202, 204, 206, 208, 210, 212, 214 and 216, and four check nodes 218, 220, 222 and 224. The variable nodes 202, 204, 206, 208, 210, 212, 214 and 216 are represented by x1, x2, . . . , xs, and if there exists 1 at the point crossed by the ith column and jth row, a branch is formed between the variable node xi and the jth check node. Thus the parity check matrix of the LDPC code has a very small number of weight 1s, so that the LDPC code may be decoded through iterative decoding even with a large block size, and with the block size being continuously increased the LDPC code begins to have performance closely approaching the channel capacity limit of Shannon as the turbo code. Mackay and Neal already verified that the LDPC code begins to have performance closely approaching that of the turbo code through iterative decoding.
Additionally, the requirements for achieving an LDPC code having good performance are as follows:
The first requirement is to make the cycle larger. The term “cycle” means a closed path that does not pass over any node twice or more in the factor graph model of the LDPC code. Namely, the greater the number of the cycles of small size, the more the LDPC code suffers performance degradation, such as an error floor. Accordingly, the longer the cycle of the LDPC code produced in the factor graph, the better the LDPC code becomes with respect to performance.
The second requirement is to consider the distribution of degrees of the LDPC code in the factor graph. Generally the reason that the irregular LDPC code has better performance than the regular LDPC code is that the nodes of the irregular LDPC code have various degrees. The term “degree” represents the number of the edges connected with the variable nodes and check nodes in the factor graph of the LDPC code. In addition, the term “distribution of degrees” represents what percentage the nodes with a particular degree occupy of the entire nodes. According to Richardson, it is well-known that the LDPC code must have a particular distribution of degree for good performance.
As described above, the LDPC code is generally expressed using the parity check matrix. Hence, the memory size may be reduced by effectively storing the information of the parity check matrix. The conventional storing of the LDPC code requires a comparatively large memory. In order to cope with this, various methods for effectively storing the LDPC code have been proposed. For example, since Fan proposed the array code with a structural parity check matrix, various quasi-cyclic LDPC (hereinafter referred to as “QC-LDPC”) codes have been developed based on the circulant permutation matrix in order to improve the memory efficiency. The QC-LDPC code is composed of a number of small blocks obtained by dividing the parity check matrix each matched with a circulant permutation matrix or a zero matrix. The QC-LDPC code is described below in connection with FIG. 3.
FIG. 3 is a diagram illustrating the parity check matrix of the QC-LDPC code. The QC-LDPC code is a new LDPC code for improving the storage and performance of the effective parity check matrix. The parity check matrix of the QC-LDPC code is formed by dividing the entire parity check matrix into a plurality of partial blocks each matched with a permutation matrix. In FIG. 3, the reference symbol P represents a permutation matrix with a size of Ns×Ns as expressed by the following Formula 1, and its superscript amn is in the range O≦amn≦Ns−1 or limitless (amn−∞), wherein “m” and “n” represent the permutation matrix of a partial block positioned at the cross point of the m'th row and the n'th column of the entire partial blocks. Namely, “m” and “n” respectively represent the row and column locating the partial block containing an information part in the parity check matrix. Formula 1 represents an example of the permutation matrix as shown in FIG. 3.
                    P        =                  [                                                    0                                            1                                            0                                                                                                                          0                                                                    0                                            0                                            1                                            ⋯                                            0                                                                    ⋮                                            ⋮                                            ⋮                                                                                                                          ⋮                                                                    0                                            0                                            0                                            ⋯                                            1                                                                    1                                            0                                            0                                                                                                                          0                                              ]                                    Formula        ⁢                                  ⁢        1            
As expressed by Formula 1, the permutation matrix P is a square matrix with a size of Ns×Ns, wherein each of the Ns rows has a weight of 1, and each of the Ns columns a weight of 1. Hereinafter the size Ns×Ns is shortened as Ns for convenience's sake because the permutation matrix P is square. In addition, if the superscript amn−O, the permutation matrix P0 means the unit matrix INs×Ns and if amn−∞, Pamn is the zero matrix O.
In the mean time, a small cycle in the LDPC code causes performance degradation. Namely, a small cycle causes the information from a node to return to itself even after a small number of repetitions, so that the same information continuously returning to it prevents an information revision resulting in degradation of the error-correction capability. Hence, the LDPC code having good performance may be obtained by increasing the size of the cycle and decreasing the number of small cycles.
FIG. 4 is a diagram illustrating the structural characteristics of the cycle of the QC-LDPC code. As described above, the QC-LDPC code is an LDPC code extended by generalizing the structure of the regular LDPC code in order to achieve effective coding and improve the storage and the performance of the effective parity check matrix.
Referring to FIG. 4, the structural characteristics of the cycle of the QC-LDPC code are analyzed with the parity check matrix consisting of four blocks. In the drawing the diagonal lines indicate the position of 1, and the remaining parts all indicate the position of 0. The symbol P represents the permutation matrix as shown in FIG. 3. Hereinafter the permutation matrixes corresponding to the partial blocks are referred to as “partial matrixes.”
For analyzing the structure of the cycle of the QC-LDPC code, 1 positioned in the ith row of the partial matrix Pa is determined as the reference point defined as “0-Point.” In this case, the 0-Point is positioned in the i+ath column of the partial matrix Pa. And 1 of the partial matrix Pb positioned in the same row as the 0-Point is defined as “1-Point.” In this case, the 1-Point is positioned in the i+bth column of the partial matrix Pb.
Then, 1 of the partial matrix Pc positioned in the same column as the 1-Point is defined as “2-Point.” Since the partial matrix Pc is obtained by displacing each column of the unit matrix I toward the right by the amount of “c” with reference to modulo Ns, the 2-Point is positioned in the i+b−cth row of the partial matrix Pc. And 1 of the partial matrix Pd positioned in the same row as the 2-Point is defined as “3-Point.” Then likewise, the 3-Point is positioned in the i+b−c+dth column of the partial matrix Pd.
Finally, 1 of the partial matrix, Pa positioned in the same column as the 3-Point is defined as “4-Point.” The 4-Point is positioned in the i+b−c+d−a th row of the partial matrix Pa. In this case, if there exists the cycle with a size of 4 in the parity check matrix of QC-LDPC code shown in FIG. 4, the 0-Point and the 4-Point occupy the same position. Namely, the relationship between the 0-Point and the 4-Point is expressed by the following Formula 3.i≡i+b−c+d−a(mod Ns) ori+a≡i+b−c+d(mod Ns)  Formula 3
Formula 3 can be rewritten as in the following Formula 4.a+c≡b+d(mod Ns)  Formula 4
Thus, if the relationship is expressed by Formula 4, there is produced a cycle with a size of 4.
Generally if the 0-Point and the 4m-Point become to equal each other for the first time, their relationship is expressed by the following Formula 5, which may be rewritten as in Formula 6.i≡i+m(b−c+d−a)(mod Ns)  Formula 5m(a−b+c−d)≡0(mod Ns)  Formula 6
Namely, if the least positive integer satisfying Formula 6 for the values of a, b, c and d given is “m”, the cycle with 4m size becomes the cycle with the minimum size in the parity check matrix of the QC-LDPC code as shown in FIG. 4. Thus, if gcd(Ns, a−b+c−d)−1 for (a−b+c−d)≠0, m−Ns, and therefore the cycle with a size of 4Ns is the cycle with the minimum size.
Generally, the irregular LDPC code requires the position information for each weight of the parity check matrix to be stored. On the contrary, the QC-LDPC code requires only the position of the first weight of the small block to be stored because the position of the first weight determines automatically the positions of the remaining Ns−1 weights in the block. Accordingly, if Ns is known, the exponent of the size m×n is only stored in order to store the information of the parity check matrix H defined as in FIG. 3. Hence, the QC-LDPC code requires the memory capacity approximately proportional to 1/Ns compared with the conventional irregular LDPC code. Meanwhile, different QC-LDPC codes require different memories for storing the parity check matrixes, so that the memory capacity must be increased for storing the parity check matrixes of several QC-LDPC codes.
Conventionally, the QC-LDPC codes of short size are stored in a memory different from one for those of long size, or the QC-LDPC codes of long size are subjected to the modulo operation so as to produce those of short size. However, if the exponent matrix is subjected to an arbitrary modulo operation, the cycle characteristics in the Tanner graph of the QC-LDPC code are significantly changed, resulting in performance degradation. In this case, if the modulo operation is performed so as to not degrade the cycle characteristics in order to avoid performance degradation, the number of the codes to be produced is greatly limited. Therefore, there has been requested a solution for generating a plurality of the QC-LDPC codes with good cycle characteristics.